397. 整数替换

Similar Question

Solution Tips

方案一: Dfs + 记忆

这里的一个数学知识点, 为了防止溢出, 使用的方法非常巧妙

var integerReplacement = function(n) {
    if (n === 1) {
        return 0;
    }
    if (n % 2 === 0) {
        return 1 + integerReplacement(Math.floor(n / 2));
    }
    return 2 + Math.min(integerReplacement(Math.floor(n / 2)), integerReplacement(Math.floor(n / 2) + 1));
};

我们给方法一的递归加上记忆化，这样递归树的每一层最多只会计算两个 n 值，时间复杂度降低为 O(logn)。

主要节省的就是 Math.min() 里的计算, 因为这两个数相差的不大, 所以难免会有很多重复的计算.

const memo = new Map();
var integerReplacement = function(n) {
    if (n === 1) {
        return 0;
    }
    if (!memo.has(n)) {
        if (n % 2 === 0) {
            memo.set(n, 1 + integerReplacement(Math.floor(n / 2)));
        } else {
            memo.set(n, 2 + Math.min(integerReplacement(Math.floor(n / 2)), integerReplacement(Math.floor(n / 2) + 1)));
        }
    }
    return memo.get(n);
};

方案二: 方案一的动态规划解释

代码一摸一样, 只是站在了不同的角度去理解这段代码

方案三: 贪心思想

我觉得太难理解了, 想进阶可以去看题解